(1) Field of the Invention
The present invention relates to a computer database method for providing an early database commit while increasing database concurrency and limiting cascading aborts to minimize the impact on recovery for a decomposed database and transaction system.
(2) Description of the Prior Art
Real-time command, control and communications (C.sup.3) systems control physical systems by extracting data from sensors, processing the extracted data, and performing control actions based on this processed data. Real-time C.sup.3 systems are applied to applications where timeliness of data access, data processing and reactive responses are critical to the applications successful operations.
Real-time C.sup.3 systems are being applied to a wide variety of physical systems, such as automotive control, aircraft control, spacecraft control, power management, automated factories, medical assistance and defense oriented systems. The main function of real-time C.sup.3 systems is to manage and utilize information to control the real world environment. Therefore, these systems can be viewed as large information management systems that must respond in predictable ways and within specified time frames.
Real-time C.sup.3 systems differ from conventional, general purpose systems in the sense that consistency and correctness of the real-time systems operation is dependent on the timeliness and predictability of responses to the controlled processes activities. In a real-time C.sup.3 system, information is repeatedly collected from the physical system. Collected information is sampled, converted, formatted, timestamped and inserted into the control computer's database for each sampling period of the systems sensors. Stored data must be provided to the control software and system operators to be acted on to produce some desired control action.
Once the data is inserted into the database, it is used to compute a variety of related parameters. For example, raw sensor inputs from a radar system can be read and reduced to a bearing, range, and speed. These data items in turn can be used to compute detailed tracks of contacts, allowing for long-term tracking of an object. In addition, the raw information can be used to compute a profile on an object being tracked. This makes possible the classification and identification of an observed object. Transactions written to accomplish these computations require predictable and correct access, but not necessarily serializable access.
Real-time computing systems are being applied to a greater variety of control applications that require timely information.
Researchers are looking towards real-time computer systems as an emerging and important discipline in computer science and engineering. The real-time systems are characterized as possessing time dependent operations, reliable hardware and software, synergy with the controlled environment, predictable service. Predictability should be maintained not only in task scheduling, but also in scheduling all assets such as input/output, processing, communications, storage, and specialized controllers.
Databases within real-time systems must satisfy not only database consistency constraints but also timing constraints associated with transactions.
Responsive real-time databases must be predictable yet timely in their service. Real-time databases must incorporate features from real-time operating systems schedulers. A means to select the most appropriate database action to perform is necessary, and the scheduler must be adaptive to an ever changing real-time systems state. For correct database operations, real-time schedulers must be integrated with high performance concurrency control algorithms.
Recovery techniques based on rollback are not adequate in a real-time environment nor are present concurrency control techniques based on locking due to added blocking delays. Transactions must use non-serializable techniques, embedded transaction semantic knowledge, decomposition of transactions and the database to form more concurrent executions.
Transactions represent the unit of work recognized by users as being atomic. "Atomic" meaning that the operation or operations must complete execution or be aborted all together. Transactions serve the dual purpose as the unit for concurrency and recovery in database systems. Concurrency provides for indivisible access to data objects by concurrently executing users; and recovery provides for data restoration due to hardware, software, and transaction failures.
Due to these properties researchers look towards the use of transactions as a tool for structuring computations in distributed systems.
Research into transaction decomposition is relatively new; however, researches have studied breaking transactions into nested elementary transactions to increase concurrency. One approach to this is to decompose transactions into disjointed operations separated by breakpoints which breakpoints define allowable interleaving to allow increased concurrency. Another approach is to decompose transactions into data flow graphs of transaction computations steps which can be optimized to increase performance.
The data itself can also be decomposed into atomic data sets (ADS) to allow a more concurrent execution of decomposed transaction steps. Many researchers indicate that a finer granularity on data objects can increase data concurrency if managed properly. Availability and timeliness of data and processing has been pointed out as being a desirable feature in real-time database management systems and may be more important that consistency. Thus, the cited research indicates using transaction decomposition, database decomposition, and parallel and concurrent execution of database actions to provide for increased performance.
Concurrency control is used to ensure database consistency while allowing a set of transactions to execute concurrently. The problem solved by concurrency control is to allow non-interfering readers and writers free access, while controlling and coordinating the actions of conflicting readers and writers. There are three basic concurrency control approaches for transaction processing in database systems: locking, timestamp ordering and optimistic. The basic concurrency control techniques rely on syntactic information to make concurrency control decisions. The correctness of the algorithms is based on serializability theory.
These concurrency control techniques are inherently pessimistic. They avoid conflicts by enforcing serialization of conflicting database actions. Prior art literature points out that serializability as a correctness criteria is to stiff a requirement for real-time systems. Real-time concurrency control algorithms, must integrate real-time scheduling algorithms with concurrency control techniques.
Semantic information about transactions can be used to develop non-serializable scheduling of transaction steps that nonetheless are correct executions. A prior art method using this breaks transactions into a collection of disjoint classes. Transactions that belong to the same class are compatible allowing for arbitrary interleaving, whereas transactions that belong to different classes are incompatible and cannot interleave. Another prior art method defines a scheme wherein the transaction writing system decomposes transactions into steps upon which concurrency control can be performed. Transactions are broken at breakpoints, and type classes defined on the breakpoints. Transactions of compatible classes can interleave at this point, others cannot. A further refinement of this technique is achieved by using a larger volume of transaction class types which results in a finer granularity of breakpoints. This system increases concurrency by adopting a looser definition of correctness than serializability.
Other prior art research suggests the use of decomposition of both transactions and the database into finer granules to increase concurrency. In this theory the database and transactions are decomposed into atomic data sets (ADS) and elementary transactions respectively. Elementary transactions are executed concurrently on distributed assets of an ADS. This theory suggests that if elementary transactions are serialized with respect to an ADS then correct and consistent database executions result.
The aforementioned schemes do not address the issues in management of real-time data which are driven by the needs of the overall system, based on criticality of operations, nature of deadlines, and timing requirements. This paper develops and presents transaction concurrency control algorithms for real-time systems, based on decomposition of both the database and individual transactions, along with the application of criticalness, deadlines, and timing requirements to improve real-time database systems performance and predictability.